// 你是一个专业的小偷，计划偷窃沿街的房屋。
// 每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
// 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
// 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额


var rob: (nums: number[]) => number = function (nums) {
    // 安全校验
    if (nums.length < 1) {
        return 0;
    }
    // 状态变量dp1的意义：上上家房屋的最佳收益值
    let dp1: number = nums[0];
    // 状态变量dp2的意义：上家房屋的最佳收益值
    let dp2: number = Math.max(nums[0], nums[1] || 0);
    for (let i = 2; i < nums.length; i++) {
        // 计算出当前房屋的最佳收益，即状态转移方程
        let currDp: number = Math.max(dp1 + nums[i], dp2);
        // 动态维护两个dp变量
        dp1 = dp2;
        dp2 = currDp;
    }
    // 结束时i = nums的数组长度，所以dp2即为结果
    return dp2;
};

        // 这道题的类型是非常经典的动态规划例题了
        // 首先按照动态规划算法的套路，我们先定义一个状态变量数组dp，
        // dp数组的每一位对应当前数组下标i时所能劫持到的最大金钱数
        // 首先当数组长度<=2时，判断非常简单，我们只要返回2个数中大的那个即可。
        // 可以在纸上画画，当数组长度>=3时，问题就开始复杂了
        // 因为此时会有两种选择，
        // 1、劫持当前房屋，那么金额就为dp[i-2]+nums[i](相邻的不能抢劫)
        // 2、不劫持当前房屋，那么金额就为dp[i-1]
        // 而这两种选择我们是需要判断一下哪种的收益是更高的
        // 当我们确定了当前收益较高的一种dp[i]之后，我们即可做下一轮的判断
        // 但是思考到这里，你可以发现这里能做一个降维处理达到状态压缩
        // 因为其实每轮判断中其实我们只需要用到dp[i-1]和dp[i-2]
        // 我们直接声明两个变量存储，然后在循环中不断维护这个变量
        // 维护的方法就是当我们确定了当前的dp[i]之后，每轮操作里我们把dp[i-1]赋值给dp[i-2]
        // dp[i]赋值给dp[i-1]，这样就达到了一个维护的效果
        // 此时的dp[i-2]的意义就是第i-2个房屋的最佳收益，dp[i-1]的意义就是第i-1个房屋的最佳收益